package com.lw.leetcode.binary.c;

/**
 * Created with IntelliJ IDEA.
 * c
 * binay
 * 1964. 找出到每个位置为止最长的有效障碍赛跑路线
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/30 9:18
 */
public class LongestObstacleCourseAtEachPosition {

    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int length = obstacles.length;
        int end = 0;
        int[] arr = new int[length];
        arr[0] = obstacles[0];
        obstacles[0] = 1;
        for (int i = 1; i < length; i++) {
            int c = end + 2;
            int t = obstacles[i];
            if (arr[end] <= t) {
                arr[++end] = t;
            } else {
                c = find(arr, t, end);
                arr[c] = t;
                c++;
            }
            obstacles[i] = c;
        }
        return obstacles;
    }

    private int find(int[] arr, int t, int end) {
        int st = 0;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (arr[m] <= t) {
                st = m + 1;
            } else {
                end = m;
            }
        }
        return st;
    }

}
